package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC732 {
    public long startExecuteTime = System.currentTimeMillis();


    class MyCalendarThree {

        class Node {
            Node left;
            Node right;
            int l;
            int r;
            int mid;
            int v;
            int add;

            public Node(int l, int r) {
                this.l = l;
                this.r = r;
                this.mid = (l + r) >> 1;
            }
        }

        class SegmentTree {
            private Node root = new Node(1, (int) 1e9 + 1);

            public SegmentTree() {

            }

            public void modify(int l, int r, int v) {
                modify(l, r, v, root);
            }

            public void modify(int l, int r, int v, Node node) {
                if (l > r) {
                    return;
                }
                if (node.l >= l && node.r <= r) {
                    node.v += v;
                    node.add += v;
                    return;
                }
                pushDown(node);

                if (l <= node.mid) {
                    modify(l, r, v, node.left);
                }
                if (r > node.mid) {
                    modify(l, r, v, node.right);
                }
                pushUp(node);
            }

            public int query(int l, int r) {
                return query(l, r, root);
            }

            public int query(int l, int r, Node node) {
                if (l > r) {
                    return 0;
                }
                if (node.l >= l && node.r <= r) {
                    return node.v;
                }
                pushDown(node);
                int v = 0;
                if (l <= node.mid) {
                    v = Math.max(v, query(l, r, node.left));
                }
                if (r > node.mid) {
                    v = Math.max(v, query(l, r, node.right));
                }
                return v;
            }

            public void pushUp(Node node) {
                node.v = Math.max(node.left.v, node.right.v);
            }

            public void pushDown(Node node) {
                if (node.left == null) {
                    node.left = new Node(node.l, node.mid);
                }
                if (node.right == null) {
                    node.right = new Node(node.mid + 1, node.r);
                }
                if (node.add != 0) {
                    Node left = node.left, right = node.right;
                    left.add += node.add;
                    right.add += node.add;
                    left.v += node.add;
                    right.v += node.add;
                    node.add = 0;
                }
            }
        }

        private SegmentTree tree = new SegmentTree();

        public MyCalendarThree() {

        }

        public int book(int start, int end) {
            tree.modify(start + 1, end, 1);
            return tree.query(1, (int) 1e9 + 1);
        }
    }


    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new MyCalendarThree().toString());
    }

    public static void main(String[] args) throws Exception {
        LC732 an = new LC732();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
